package com.cn.codebrush.数组.双指针;

import java.util.Deque;
import java.util.LinkedList;

public class No42接雨水 {
    public static void main(String[] args) {
        int[] nums = {4,2,0,3,2,5};
        System.out.println(trap2(nums));
    }


    /**
     * 双指针
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int n = height.length;
        int left =0;
        int right = n-1;
        int leftMax =0;
        int rightMax =0;
        int sum  = 0;
        while (left<=right){
            if(leftMax > rightMax){
                rightMax = Math.max(rightMax,height[right]);
                sum += rightMax - height[right];
                right--;
            }else {
                leftMax = Math.max(leftMax,height[left]);
                sum += leftMax - height[left];
                left++;
            }
        }

        return sum;
    }


    /**
     * 单调栈
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0;
        for(int right =0;right<height.length;right++){
            while (!deque.isEmpty() && height[deque.peek()]<height[right]){
                int bottom = deque.poll();
                if(deque.isEmpty()){break;}
                int left = deque.peek();
                sum += (right-left-1)*(Math.min(height[left],height[right])-height[bottom]);
            }

            deque.push(right);
        }

        return sum;
    }

}
